# from pandas import np
import copy

import numpy


def get_len(ll):
    count = 0
    for i in ll:
        count += 1
        # print(count)
    return count


def check(ll):
    for i in range(len(ll) - 1):
        if ll[i] > ll[i + 1]:
            return False
    return True


def sort01(ll):
    count = 0
    # 从左向右冒泡
    length = get_len(ll)
    sorted_flag_l_to_r = True
    # 有序右边界下标
    b_right = length - 1
    for i in range(length):
        for j in range(b_right):
            count += 1
            if ll[j] > ll[j + 1]:
                ll[j], ll[j + 1] = ll[j + 1], ll[j]
                b_right = j
                sorted_flag_l_to_r = False
        if sorted_flag_l_to_r:
            break
    return count


def sort02(ll):
    count = 0
    # 从右向左冒泡
    length = get_len(ll)
    sorted_flag_r_to_l = True
    # 有序左边界下标
    b_left = 0
    for i in range(length):
        for j in range(length - 1, b_left, -1):
            count += 1
            # print(j, j - 1)
            if ll[j] < ll[j - 1]:
                ll[j], ll[j - 1] = ll[j - 1], ll[j]
                b_left = j
                sorted_flag_r_to_l = False
        # print('-' * 5)
        if sorted_flag_r_to_l:
            break
    return count


def sort03(ll):
    count = 0
    # 两边冒泡
    length = len(ll)
    sorted_flag_l_to_r = True
    # 有序右边界下标
    b_right = length - 1

    sorted_flag_r_to_l = True
    # 有序左边界下标
    b_left = 0

    # 两测一起向中心移动, 只需要遍历一半
    for i in range(length//2):
        # 从左向右冒泡
        for j in range(b_right):
            if ll[j] > ll[j + 1]:
                ll[j], ll[j + 1] = ll[j + 1], ll[j]
                b_right = j
                sorted_flag_l_to_r = False
        # 从右向左冒泡
        for j in range(length - 1, b_left, -1):
            count += 1
            # print(j, j - 1)
            if ll[j] < ll[j - 1]:
                ll[j], ll[j - 1] = ll[j - 1], ll[j]
                b_left = j
                sorted_flag_r_to_l = False
        # print('-' * 5)
        if sorted_flag_r_to_l or sorted_flag_l_to_r:
            break
    return count


def check_all(f, times):
    for _ in range(times):
        # create a random list
        # randint(low,high,size,dtype)
        lb = numpy.random.randint(-100, 100, size=10)
        f(lb)
        # print(lb)
        if not check(lb):
            print(lb)
            return False
    return True


if __name__ == '__main__':
    print(check_all(sort03, 100))
    l1 = [-85, -33, -54, -76, 97, -12, 54, -65, 84, 20, 84, -38, 45, 67, 73]
    # l1 = numpy.random.randint(-100, 100, size=100)
    # l2 = copy.deepcopy(l1)
    l3 = copy.deepcopy(l1)
    # print(sort01(l1), check(l1))
    # print(sort02(l2), check(l2))
    print(sort03(l3), check(l3))
